package wjl.leetcode;

import java.util.Arrays;

/**
 * 寻找两个正序数组的中位数:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
 * 
 * @author Wjl
 *
 */
public class FindMedianSortedArrays {
    public static void main( String[] args ) {
        int[] nums1 = {1, 3};
        int[] nums2 = {2, 3};
        System.out.println( findMedianSortedArrays2( nums1, nums2 ) );
    }

    /*
     * 执行用时：4 ms, 在所有 Java 提交中击败了18.70%的用户
     * 内存消耗：39.9 MB, 在所有 Java 提交中击败了48.83%的用户
     */
    public static double findMedianSortedArrays1( int[] nums1, int[] nums2 ) {
        int[] nums = Arrays.copyOf( nums1, nums1.length + nums2.length );
        System.arraycopy( nums2, 0, nums, nums1.length, nums2.length );
        Arrays.sort( nums );
        int    len = nums.length;
        double d;
        if ( len % 2 == 0 ){
            d = (nums[(len - 1) / 2] + nums[((len - 1) / 2) + 1]) / 2d;
        } else{
            d = nums[(len - 1) / 2];
        }
        return d;
    }

    public static double findMedianSortedArrays2( int[] nums1, int[] nums2 ) {
        double d;
        int[]  nums = new int[nums1.length + nums2.length];
        for ( int i = 0; i < nums1.length; i++ ){
            nums[i] = nums1[i];
        }
        for ( int i = 0; i < nums2.length; i++ ){
            nums[nums1.length + i] = nums2[i];
        }
        Arrays.sort( nums );
        int len = nums.length;
        if ( len % 2 == 0 ){
            d = (nums[(len - 1) / 2] + nums[((len - 1) / 2) + 1]) / 2d;
        } else{
            d = nums[(len - 1) / 2];
        }
        return d;
    }
}
